package HighMethod01;

public class test05Work {

    /**
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     */
    public static int BinaryFindValue(int[] ar, int val) {
        if (ar == null || ar.length == 0) return -1;

        int left = 0, right = ar.length - 1;
        int pos = -1;
        while (left <= right) // while(left < right)
        {
            int mid = (left + right) / 2; // mid = (right - left)/2 + left;
            if (val < ar[mid]) {
                pos = mid;
                right = mid - 1;
            } else if (val > ar[mid]) {
                pos = mid + 1;
                left = mid + 1;
            } else {
                //最左查找
                while (mid > left && ar[mid - 1] == val) --mid;

                pos = mid;
                break;
            }
        }
        return pos;
    }


    /**
     * 小明的父母要出差N天，走之前给小明留下了M块奶糖,小明决定每天吃的奶糖数量不少于前一天吃的一半，但是他又不想在父母回来之前的某一天
     * 没有奶糖吃,请问他第一天最多能吃多少块奶糖。
     */
    public static int getMaxCount(int day, int num) {
        int left = 1, right = num;
        while (left <= right) {
            boolean enough = true;

            int mid = (right - left) / 2 + left;
            int remain = num;
            int eat = mid;

            for (int i = 1; i < day; i++) {
                if (remain < eat) {
                    enough = false;
                    break;
                }
                remain = remain - eat;
                eat = (eat + 1) / 2;
            }

            if (enough) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
//        System.out.println(right); //TODO:一定返回的是右下标
        return right;
    }


    /**
     * 寻找旋转排序数组中的最小值。假设升序排序的数组在预先未知的某个点上进行了旋转。例如: 数组 {10,11,12,13,14,15,16,17} 可能变
     * 为 [14,15,16,17,10,11,12,13}；请找出其中最小的元素。假设数组中不存在重复元素。
     */
    public static int getMinFromRotateArr(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (arr[mid] > arr[right]) {
                left = mid + 1;
            }
//        else if(arr[mid] < arr[right]){
//            right = mid - 1; //此判断条件可与else合二为一
//        }
            else {
                //当arr[mid] == arr[right]时，left == right 使right-1退出循环,可与上方条件判断合二为一
                right = mid - 1;
            }
        }
        return arr[left]; //TODO:因为退出循环时right被-1，所以返回left
    }


    public static void main(String[] args) {
//                   0 1 2 3 4 5 6 7 8 9
/*        int arr[] = {1,2,2,3,4,7,7,7,8,9};
        int value = 10;
        int value2 = 0;
        int value3 = 4;
        int value4 = 5;
        System.out.println("非递归方式："+BinaryFindValue(arr,value));
        System.out.println("非递归方式："+BinaryFindValue(arr,value2));
        System.out.println("非递归方式："+BinaryFindValue(arr,value3));
        System.out.println("非递归方式："+BinaryFindValue(arr,value4));*/



        //出差4天,7块糖
        int M = 7;
        int N = 4;
        System.out.println("结果是"+ getMaxCount(N, M));



        int arr1[] = {10, 11, 12, 13, 14, 15, 16, 17};
        int arr2[] = {14, 15, 16, 17, 10, 11};
        System.out.println("旋转前最小值："+getMinFromRotateArr(arr1));
        System.out.println("旋转后最小值："+getMinFromRotateArr(arr2));

    }
}
